/**
 * @Author Fizz Pu
 * @Date 2021/4/26 下午4:25
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 并差集就是求最大联通分量的问题
 */


public class UnionAndSet {
    private int[] obs;

    public UnionAndSet(int capacity) {
        this.obs = new int[capacity];
        for(int i = 0; i < capacity; i++){
            obs[i] = -1;
        }
    }

    public int find(int ele){
        /*
        if(obs[ele] == -1){
            return ele;
        }
        return find(obs[ele]);
        */
        int parent = obs[ele];
        int child = ele;
        while (parent != -1){
            child = parent;
            parent = obs[child];
        }
        // 进行路径压缩
        // obs[ele] = child;
        return child;
    }

    public void union(int x, int y){
        int root1 = find(x);
        int root2 = find(y);
        obs[root1] = root2;
    }

    public int getCount(){
        int count = 0;
        int len = obs.length;
        for (int ob : obs) {
            if (ob == -1) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] data = new int[][]{
                {1, 1, 0},
                {1,1, 0},
                {0, 0, 1}
        };

        UnionAndSet unionAndSet = new UnionAndSet(data.length);
        for(int i = 0; i < data.length; i++){
            for(int j = i + 1; j < data[i].length; j++){
                if(data[i][j] == 1){
                    unionAndSet.union(i, j);
                }
            }
        }
        System.out.println(unionAndSet.getCount());
    }
}
